package org.huawei260.OD260;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

/**
 * @Auther: qingle
 * @Date: 2024/8/23-2:17
 * @Description:
 * @version: 1.0
 */
public class O0018_最小步骤数 {
		public static int findMinimumSteps(int[] nums) {
			if (nums == null || nums.length == 0) {
				return -1;
			}

			int n = nums.length;
			Set<String> visited = new HashSet<>(); // 用于记录访问过的索引和步数组合
			Queue<int[]> queue = new LinkedList<>(); // 使用数组存储索引和步数
			queue.offer(new int[]{0, 0}); // 初始状态，索引0，步数0

			while (!queue.isEmpty()) {
				int[] current = queue.poll();
				int currentIndex = current[0];
				int currentSteps = current[1];

				// 检查是否到达最后一个元素
				if (currentIndex == n - 1) {
					return currentSteps;
				}

				// 检查所有可能的下一步
				for (int i = 1; i < nums[currentIndex]; i++) {
					int nextIndex = currentIndex + i;
					if (nextIndex < n && !visited.contains(nextIndex + "_" + currentSteps)) {
						visited.add(nextIndex + "_" + currentSteps);
						queue.offer(new int[]{nextIndex, currentSteps + 1});
					}
				}
			}

			return -1; // 如果无法到达，返回-1
		}

		public static void main(String[] args) {
//			int[] nums = {7, 5, 9, 4, 2, 6, 8, 3, 5, 4, 3, 9};
			Scanner scanner = new Scanner(System.in);

			String[] nums = scanner.nextLine().split(" ");
			int[] numsin = new int[nums.length];
			for (int i = 0; i < nums.length; i++) {
				numsin[i] = Integer.parseInt(nums[i]);
			}

			System.out.println("Minimum steps: " + findMinimumSteps(numsin));
		}
	}